package com.cdy.demo.algorithm;

import java.util.Arrays;

public class Leetcode32 {

    public static void main(String[] args) {
        Leetcode32 leetcode32 = new Leetcode32();
        leetcode32.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4});
        leetcode32.maxSubArray(new int[]{-1,-2});
    }

    public int findMaxForm(String[] strs, int m, int n) {

        return 0;

    }


    /**
     * 53. 最大子序和
     */
    public int maxSubArray(int[] nums) {

        int len = nums.length;
        int[] max = new int[len];
        max[0] = nums[0];
        if (len == 1) {
            return nums[0];
        }
        int maxNum = nums[0];
        for (int i = 1; i < len; i++) {
            int num = nums[i];
            int max1 = max[i - 1];

            if (num >= 0) {
                if (max1 < 0) {
                    max[i] = num;
                } else {
                    max[i] = num + max1;
                }
            } else {
                if (max1 < 0) {
                    max[i] = num;
                } else {
                    max[i] = num + max[i - 1];
                }
            }
            maxNum = Math.max(maxNum, max[i]);

        }
        return maxNum;
    }
}
